By way of background, the Internet Protocol (IP) is a data-oriented protocol used for communicating data across a packet-switched internetwork. IP is a network layer protocol of the Internet protocol suite, which is encapsulated in the data link layer protocol. As a lower layer protocol, IP provides the service of communicable unique global addressing amongst computers of a network, such as the Internet.
Data from an upper layer protocol is encapsulated inside one or more packets, also referred to as datagrams. Unlike Public Switched Telephone Networks (PSTNs), with packet-switched networks, no specific connection or setup is needed before one host tries to send packets to another host with which it has not communicated previously. In this regard, IP is considered a connectionless protocol since messages can be sent to any device whose address is specified with an IP address.
Because of encapsulation, IP can be used over heterogeneous network(s), i.e., two computers can connect via any mixture or variety of disparate kinds of networking technologies, e.g., any one or more of Ethernet, asynchronous transfer mode (ATM), Fiber Distributed Data Interface (FDDI), cable, Wi-Fi, token ring, etc., and it makes no difference to the upper layer protocols. Address resolution of IP addresses to data link addresses is handled by the Address Resolution Protocol (ARP).
At bottom, IP provides an unreliable service, however since it provides a best effort delivery as opposed to guaranteed delivery. This means that the network makes no guarantees about what happens to packets and none, some, or all of the following may apply, without applying more stringent rules at the routers or endpoints: data corruption, packets arrive out of order sent, duplicate arrival or lost or dropped/discarded packets. The primary reason for the lack of reliability is owed to an original design that sought to reduce the complexity of routers needed to support IP traffic.
Routers thus have carte blanche to do as they please with packets, though anything less than best efforts yields a poor experience for the user. So, even though no guarantees are made, the better the effort made by the network, the better the experience for the user, which places a heavy burden on routers.
More generally, routing is defined as the process of selecting paths in a network along which to send data. Routing is performed for many kinds of networks, including the telephone network, the Internet, and transport networks. Routing directs the forwarding, or the passing, of logically addressed packets from their source toward their ultimate destination through intermediary nodes, routers, bridges, gateways, firewalls, switches, etc.
Routing schemes differ in their delivery semantics: unicast delivers a message to a single specified node; broadcast delivers a message to all nodes in the network; multicast delivers a message to a group of nodes that have expressed interest in receiving the message; and anycast delivers a message to any one out of a group of nodes, typically the one nearest to the source. Unicast is the dominant form of message delivery on the Internet, i.e., typically communications involve one node sending another node a message, or vice versa.
Today, the routing process directs forwarding based on routing tables, which maintain a record of the routes to various network destinations. Thus constructing routing tables, which are held in the routers' memory, becomes very important for efficient routing. Small networks may involve manually configured routing tables, while larger networks involve complex topologies and may change rapidly, making the manual construction of routing tables infeasible.
Today's routing is also complicated by the fact that no single entity is responsible for selecting paths: instead, multiple entities, such as different ISPs, are involved in selecting paths or even parts of a single path. Complications or inefficiency can result if these entities choose paths to optimize their own objectives selfishly, which may conflict with the objectives of other participants.
In this regard, several themes emerge about the original design of the Internet that are in conflict with present computing trends and network uses. First, it was originally assumed that content is located at a single, static location. Second, it was assumed that, while clients and servers may join or leave the network, routes between existing clients and servers are relatively fixed. Lastly, as evidenced by the choice to leave routing responsibility with routers, operated by disparate parties, it was assumed that in fact full network state can be managed responsibly by the routers themselves.
However, increasingly, these assumptions are being challenged by actual network usage. Advancements in networking speeds have untethered content from any one location by allowing it to be widely distributed, easily copied or moved to other machines. The numbers of hardware elements comprising the network and independent network entities operating them have also exploded, making routing a living, breathing organism that is subject to rapid change across all of the paths of the network, making path quality difficult to predict.
Additionally, a main feature of IPv6 (Internet Protocol version 6) that is driving adoption today is the larger address space: addresses in IPv6 are 128 bits long versus 32 bits in IPv4. The larger address space avoids the potential exhaustion of the IPv4 address space without the need for network address translation (NAT) and other devices that break the end-to-end nature of Internet traffic. It also makes administration of medium and large networks simpler, by avoiding the need for complex subnetting schemes. However, IPv6 is quickly challenging the assumption that full network state can be maintained by routers due to significant increases in overhead. For instance, any state information that exponentially increases with the number of endpoints will quickly explode the sheer amounts of data that a router must track for different endpoints, e.g., according to end-to-end routing techniques.
It would thus be desirable to provide a network routing system that is free from the constraints of original Internet design. Specifically, it would be desirable to provide a system that assumes desired content can be located anywhere in the network, not at any one machine, or any set of static locations. It would be further desirable to provide a system that routes between nodes as routes between nodes constantly evolve. It would be further desirable to free routers from maintaining increasingly overwhelming amounts of network state.
Accordingly, as the above background illustrates, network routing in the current Internet infrastructure no longer maps well to the way content has come to be distributed across an increasingly complex evolving network topology. Thus, more effective techniques for routing between any endpoint requesting content and a host of devices who can provide the content in the network are desired. The above-described deficiencies of network routing techniques are merely intended to provide an overview of some of the problems of conventional systems, and are not intended to be exhaustive. Other problems with the state of the art and corresponding benefits of the invention may become further apparent upon review of the following description of various non-limiting embodiments of the invention.